package com.fw.algorithm.sort;

/**
 * 排序算法 - 冒泡排序
 */
public class BubblingSort {


   /* public static void main(String[] args) {
        int[] arr = new int[]{1,-20,2,-30,7,18,6,5,21,89,100,99};
        BubblingSort bubblingSort = new BubblingSort();
        for (int i : arr) {
            System.out.printf("%d\t",i);
        }
        System.out.println();
        bubblingSort.sortFinalArr(arr);
        for (int i : arr) {
            System.out.printf("%d\t",i);
        }
        System.out.println();

    }*/

    /**
     * 优化版冒泡排序
     * @param arr
     */
    private void sortFinalArr(int[] arr){
        // 优化标示
        /**
         * 如果内部一次交换的逻辑都没有，说明已经没有可交换的，直接退出即可。
         */
        boolean flag = false;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length -1 -i; j++) {
                flag = true;
                int perTemp =  arr[j];
                int nextTemp = arr[j+1];
                if (perTemp > nextTemp){
                    // 置换
                    arr[j] = nextTemp;
                    arr[j+1] = perTemp;
                }

            }
            if (!flag){
                break;
            }

        }


    }

    /**
     * 冒泡排序 时间复杂度 O(n2)
     * 左右比较，相邻的元素，进行逆序，置换。
     * @param arr
     */
    private void sortArr(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            //第 n次交换
            for (int j = 1; j < arr.length - i; j++) {
                int perTemp =  arr[j-1];
                int nextTemp = arr[j];
                if (perTemp > nextTemp){
                    // 置换
                    arr[j-1] = nextTemp;
                    arr[j] = perTemp;
                }
            }
        }
    }

    /**
     * 思路刨析冒泡排序
     *
     * 1. 8,7,100,88,99
     * 2. 第一次排序，把 8，7 拿出来比较，进行逆序
     * 3. 最终变成为 7,5,8,88,99
     * 4. 第二次排序 5,7,8,88,99
     * 5. 第三次排序 5,7,8,88,99 ... 此处参考优化冒泡
     *
     * 由此可看出，此时只需要在包含一次for循环就不用在此无限极排序。 规律已钉死。
     */

    public static void main(String[] args) {
        int[] arr = new int[]{8,7,5,88,99};
        // 为什么减1 要知道，你每次执行这个循环需要拿到的是 当前索引 以及下一个索引，
        // 按照这种思路推理，等你拿到 索引 3 的时候，next 下一个就是索引 4。
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i +1]){
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }

        for (int i : arr) {
            System.out.printf("%d\t",i);
        }
        System.out.println();

    }


}
